
package com.kube;
import com.kube.MD5;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;

public class army{
	static int n;   //閮ㄨ惤鎴愬憳鏁�
	static int b;
	static int[][] c;
	static int bestb;
	static int[] w; //褰撳墠閮ㄨ惤鍐涢槦闆嗗悎
	static int[] bestw;   //鏈�浜烘椂鐨勬垚鍛�
	static int[] c1;// = {1,1,2,2,2,2,3,3,4,5 };	//浠囦汉绗竴鍒梴1,1,2,2};//
	static int[] c2 ;//= {2,4,3,4,5,6,5,6,5,6 };	//浠囦汉绗簩鍒梴2,4,3,4};//
	public static void main(String args[]){
		
		 String s = new String("a");   
		  System.out.println("原始：" + s);   
		  System.out.println("MD5后：" + MD5.MD5(s));

		  System.out.println("MD5后再加密：" + MD5.KL(MD5.MD5(s)));   
		  System.out.println("解密为MD5后的：" + MD5.JM(MD5.KL(MD5.MD5(s))));   
		read();
		find(c1,c2);
		maxPerson();
		write();
		for(int ww:bestw){
			System.out.print(ww);
		}
	}
	
	private static void find(int[] c1, int[] c2){
		c = new int[n][c2.length];
		for(int i=0; i<c1.length; i++){
			c[c1[i]-1][i] = c2[i];
		}
		
		for(int i=0;i<c2.length;i++){
			c[c2[i]-1][i] = c1[i];
		}
		
		/*for(int i=0; i<c.length; i++){
			for (int j=0; j<c[i].length; j++){
				System.out.print(c[i][j]);
			}
			System.out.println();
		}*/
	}	
	public static void maxPerson(){
		//鍒濆鍖栧弬鏁�
		b=0;
		bestb=0;
		w = new int[n];
		bestw = new int[n];
		backtrack(1);
	}
	private static boolean isConflicting(int i) {
		for(int j=0;j<c[i-1].length;j++){
			for(int k = 0; k < w.length; k++){
				//System.out.println(i+"  "+w[k]);
				if(w[k]!=0&&c[i-1][j]==w[k]) {
					//System.out.println(i+"true"+w[k]);
					return true;
				}
			}
		}
		return false;
	}
	
	private static void backtrack(int i) {
		//鎼滅储绗琲灞傝妭鐐�
		if(i>n){//鍒拌揪鍙跺瓙鑺傜偣
			if(b > bestb){
				bestb = b;
				/*for(int m = 0; m<bestw.length; m++){
					bestw[m] = w[m];
				}*/
				bestw = w.clone();
			}
			return;
		}
		
		//鎼滅储瀛愭爲,濡傛灉娌℃湁鍐茬獊寰�笅鎼滅储锛屾湁鍐茬獊鐩存帴鑸嶅純
		if(!isConflicting(i)){
			w[i-1]=i;
			b++;
			backtrack(i+1);
			b--;
			w[i-1] = 0;
		}
		backtrack(i+1);
	}
	
	private static void write(){
		FileOutputStream fos = null;
		try {
			File f = new File("e:\\output.txt");
			fos = new FileOutputStream(f);
			for(int ww:bestw){
				fos.write((ww+"").getBytes());
			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}finally{
			try {
				fos.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}
	private static void read(){
		FileInputStream fis =null;
		try{
			File f = new File("e:\\input.txt");
			fis = new FileInputStream(f);
			byte[] b = new byte[1024];
			int i = 0;
			while((i=fis.read(b))>0){
				String str = new String(b,0,i);
				//System.out.println(str);
				String[] s = str.split(" ");
				n = Integer.parseInt(s[0]);
				int relationNum = Integer.parseInt(s[1]);
				c1 = new int[relationNum];
				c2 = new int[relationNum];
				for(int j=0; j<relationNum;j++){
					c1[j] = Integer.parseInt(s[3+j]);
				}
				for(int j=0; j<relationNum;j++){
					c2[j] = Integer.parseInt(s[4+relationNum+j]);
				}
			}
		}catch(Exception e){
			e.printStackTrace();
		}finally{
			try {
				fis.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}
}